/*
 * 查找s中完整包含t的最小子字符串
 * https://leetcode-cn.com/problems/minimum-window-substring/submissions/
 */

typedef struct {
    int ch;
    int cnt;
    UT_hash_handle hh;
} ut_hash_t;

ut_hash_t *window = NULL;
ut_hash_t *need = NULL;

void add_need_int(int ch);
ut_hash_t *find_need_int(int ch);
ut_hash_t *add_window_int(int ch);
ut_hash_t *find_window_int(int ch);

char *minWindow(char *s, char *t)
{
    window = NULL;
    need = NULL;

    for (int i = 0; i < strlen(t); i++) {
        add_need_int(t[i]);
    }

    int left = 0, right = 0;
    int valid = 0;
    int s_len = strlen(s);
    int start = 0, min_len = INT_MAX;

    while (right < s_len) {
        char c = s[right];
        right++;
        ut_hash_t *need_c = find_need_int(c);
        if (need_c != NULL && need_c->cnt > 0) {
            ut_hash_t *window_c = add_window_int(c);
            if (need_c->cnt == window_c->cnt) {
                valid++;
            }
        }

        while (valid == HASH_COUNT(need)) {
            if (right - left < min_len) {
                start = left;
                min_len = right - left;
            }
            char d = s[left];
            left++;
            ut_hash_t *n_c = find_need_int(d);
            if (n_c != NULL && n_c->cnt > 0) {
                ut_hash_t *w_c = find_window_int(d);
                if (w_c != NULL && w_c->cnt == n_c->cnt) {
                    valid--;
                }
                w_c->cnt--;
            }
        }
    }
    if (min_len == INT_MAX) return "";
    char *res = (char *)calloc(min_len + 1, sizeof(char));
    strncpy(res, s + start, min_len);
    return res;
}

void add_need_int(int ch)
{
    ut_hash_t *s = NULL;
    HASH_FIND_INT(need, &ch, s);
    if (s == NULL) {
        s = (ut_hash_t*)malloc(sizeof(*s));
        s->ch = ch;
        s->cnt = 0;
        HASH_ADD_INT(need, ch, s);
    }
    s->cnt++;
}
ut_hash_t *find_need_int(int ch)
{
    ut_hash_t *s = NULL;

    HASH_FIND_INT(need, &ch, s);

    return s;
}
ut_hash_t *find_window_int(int ch)
{
    ut_hash_t *s = NULL;

    HASH_FIND_INT(window, &ch, s);

    return s;
}
ut_hash_t *add_window_int(int ch)
{
    ut_hash_t *s = NULL;
    HASH_FIND_INT(window, &ch, s);
    if (s == NULL) {
        s = (ut_hash_t *)malloc(sizeof(*s));
        s->ch = ch;
        s->cnt = 0;
        HASH_ADD_INT(window, ch, s);
    }
    s->cnt++;
    return s;
}